package leetcode_动态规划._09字符串编辑;

/**
 * @author yzh
 * @data 2021/3/21 16:55
 * 两个字符串的删除操作
 * 思路：
 *   动态规划
 *   从空字符串开始
 *   dp[i][j] --- 表示 s1 的前 i 个字符串和 s2 的前 j 个字符串相等所需的步骤
 *   dp 数组初始化：当 s1 为空字符串时，需要的步骤是 s2 字符串的个数；s2 同 s1
 *   当两个字符串中的字符不相等时，dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j]) + 1
 *   相等时，dp[i][j] = dp[i - 1][j - 1]
 *   |      | ''   | e    | a    | t    |
 *   ---- ---- ---- ---- ---- ---- ---- -
 *   | ''   | 0    | 1    | 2    | 3    |
 *   | s    | 1    | 2    | 3    | 4    |
 *   | e    | 2    | 1    | 2    | 3    |
 *   | a    | 3    | 2    | 1    | 2    |
 */
public class _583 {

    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i <= n; i++) {
            dp[0][i] = i;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
                else dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        System.out.println(new _583().minDistance_upgrade("sea", "eat"));
    }

    /* 使用滚动数组，2 * n
     * 当 flag 作为当前改动的那一行
     * flag = 1，要 -1
     * flag = 0，要 +1
     */
    public int minDistance_upgrade(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[2][n + 1];
        for (int i = 0; i <= n; i++) dp[0][i] = i;
        int flag = 1;
        for (int i = 1; i <= m; i++) {
            dp[flag][0] = i;
            int direct = flag == 1 ? -1 : 1;
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) != word2.charAt(j - 1))
                    dp[flag][j] = Math.min(dp[flag + direct][j], dp[flag][j - 1]) + 1;
                else dp[flag][j] = dp[flag + direct][j - 1];
            }
            flag = (flag + 1) % 2;
        }
        return dp[(flag + 1) % 2][n];
    }

}
